/*
 * 堆排：
 * 1、大堆排升序（小堆排降序）
 * 2、向上调整法建堆O(NlogN)
 *    向下调整法建堆O(N)
 *
 * 这里建大堆
*/


#include <iostream>
#include <vector>
#include <ctime>

void Print(const std::vector<int>& res)
{
  for(auto e : res){
    std::cout << e << " ";
  }

  std::cout << std::endl;
}

//向下调整法
void AdjustDown(std::vector<int>& res, int parent, int end)
{
  int child = (parent << 1) + 1;
  while(child < end){
    if(child + 1 < end && res[child] < res[child + 1]) child++;
    if(res[child] > res[parent]) std::swap(res[child], res[parent]);
    else break;

    parent = child;
    child = (child << 1) + 1;
  }
}

//向上调整法
void AdjustUp(std::vector<int>& res, int child)
{
  int parent = (child - 1) >> 1;
  while(child > 0){
    if(res[child] > res[parent]) std::swap(res[parent], res[child]);
    else break;

    child = parent;
    parent = (child - 1) >> 1;
  }
}

//堆排(向上调整)
void UpHeapSort(std::vector<int>& res)
{
  for(int i = 1; i < (int)res.size(); i++){
    AdjustUp(res, i);
  }

  for(int i = 0; i < (int)res.size(); i++){
    AdjustDown(res, 0, res.size() - i);
    std::swap(res[0], res[res.size() - i - 1]);
  } 
}

//堆排(向下调整)
void DownHeapSort(std::vector<int>& res)
{
  int parent = (res.size() - 1) >> 1;
  //for(int i = 0; i <= parent; i++){
  //  AdjustDown(res, parent - i, res.size());
  //}
  for(int i = 0; i <= parent; i++){
    AdjustDown(res, i, res.size());
  }

  for(int i = 0; i < (int)res.size(); i++){
    AdjustDown(res, 0, res.size() - i);
    std::swap(res[0], res[res.size() - i - 1]);
  }
}

//测试
void TestHeapSort()
{
  std::vector<int> res1;
  for(int i = 0; i < 100; i++){
    res1.push_back(rand() % 100 + 1);
  }
  std::vector<int> res2(res1.begin(), res1.end());

  UpHeapSort(res1);
  Print(res1);
  
  DownHeapSort(res2);
  Print(res2);
}

int main()
{
  srand((unsigned long)time(nullptr));
  TestHeapSort();
  return 0;
}
